package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

import java.util.Scanner;

/**
请设计一种算法，解决著名的n皇后问题。
这里的n皇后问题指在一个n*n的棋盘上放置n个棋子，
使得每行每列和每条对角线上都只有一个棋子，求其摆放的方法数。

给定一个int n，请返回方法数，保证n <= 15
 */
public class hDFS_N皇后问题by回溯and剪枝 {
	int count = 0;//摆放的方法数
	
	public static void main(String[] args) {
		hDFS_N皇后问题by回溯and剪枝 test = new hDFS_N皇后问题by回溯and剪枝();
		test.useDFS_queen();
	}
	
	/**
	 * 前置方法
	 */
	public void useDFS_queen() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] recall = new int[n];
		DFS_Nqueen(recall, 0, n);
		System.out.println(count);
	}
	
	/**
	 * 核心语句
	 * 递归形式
	 * @param recall
	 * @param row
	 * @param n
	 */
	public void DFS_Nqueen(int[] recall, int row, int n) {
		if (row == n) {
			count++;
			return;
		}
		for (int col = 0; col < n; col++) {
			if (check(recall, row, col, n)) {//剪枝
				recall[row] = col;
				DFS_Nqueen(recall, row + 1, n);
				recall[row] = 0;//回溯；这里也可以不写
				/*
				这里可以不写回溯的原因
				与数独游戏中把回溯放for循环外面是一个道理
					每次旧col的这一次尝试，结果失败了，
					我们肯定要进行新col尝试对吧！
					这个新的col呢，
						因为recall[]是一维数组，我们尝试新col的时候，row是不变的，
						意思就是说我们把新col直接替换了旧col，
						旧尝试：recall[row] = 旧col;
						新尝试：recall[row] = 新col;覆盖掉了
						所以写不写回溯都无所谓了。
						所以老师才让自己去分析
				 */
			}
		}
	}
	
	/**
	 * 检查方法的核心语句
	 * @param recall
	 * @param targetRow
	 * @param targetCol
	 * @param n
	 * @return
	 */
	public boolean check(int[] recall, int targetRow, int targetCol, int n) {
		for (int row = 0; row < targetRow; row++) {//对每个行row都去检查
			if (recall[row] == targetCol) {//如果row上的列recall[row](此数值的意义是col) == 要被检查的列targetCol
				return false;//证明[row,recall[row]]存在皇后，无法放置新皇后
			}
			if (recall[row] + row == targetCol + targetRow) {//副对角线；[x,y]如果与[m,n]在同一副对角线，那么x+y == m+n
				return false;
			}
			if (recall[row] - row == targetCol - targetRow) {//主对角线；[x,y]如果与[m,n]在同一主对角线，那么x-y == m-n
				return false;
			}
		}
		return true;
	}
}
